import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 98152
 * Date: 2024-11-03
 * Time: 15:08
 */
public class Sort {
    public void insertSort(int[] arr) {
        for(int i = 1; i < arr.length; i++) {
            int j = i - 1;
            int tmp = arr[i];
            while(j >= 0) {
                if(arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
                j--;
            }
            arr[j+1] = tmp;
        }
    }

    public void shellSort(int[] arr) {
        int gap = arr.length;
        while(gap > 0) {
            gap /= 2;
            for(int i = gap; i < arr.length;i++) {
                int tmp = arr[i];
                int j = i - gap;
                while(j >= 0) {
                    if(arr[j] > tmp) {
                        arr[j+gap] = arr[j];
                    }else {
                        break;
                    }
                    j -= gap;
                }
                arr[j+gap] = tmp;
            }
        }
    }

    public void selectSort1(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for(int j = i+1; j < arr.length; j++) {
                if(arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            swap(arr,i,minIndex);
        }
    }

    public void selectSort(int[] arr) {
        int left = 0;
        int right = arr.length-1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = right;
            for(int i = left+1; i <= right; i++) {
                if(arr[i] < arr[minIndex]) {
                    minIndex = i;
                }
                if(arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(arr, minIndex, left);
            //最大值正好是  left下标  此时 把最大值换到了minIndex的位置了!!!
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(arr, maxIndex, right);
            left++;
            right--;
        }
    }

    private void swap(int[] arr, int i, int minIndex) {
        int tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
    }

    public void heapSort(int[] arr) {
        createHeap(arr);
        int end = arr.length-1;
        while(end > 0) {
            swap(arr, 0, end);
            siftDown(arr, 0, end);
            end--;
        }
    }

    private void createHeap(int[] arr) {
        for(int parent = (arr.length-1-1)/2; parent >= 0; parent--) {
            siftDown(arr, parent, arr.length);
        }
    }

    private void siftDown(int[] arr, int parent, int length) {
        int childMax = 2*parent+1;
        while(childMax < length) {
            if(childMax+1 < length && arr[childMax] < arr[childMax+1]) {
                childMax = childMax+1;
            }
            if(arr[parent] < arr[childMax]) {
                swap(arr, parent, childMax);
                parent = childMax;
                childMax = 2*parent+1;
            }else {
                break;
            }
        }
    }
    public void bubbleSort(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            boolean flag = true;
            for(int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                    flag = false;
                }
            }
            if(flag) {
                break;
            }
        }
    }

    public void quickSort(int[] arr) {
        quickNor(arr, 0, arr.length-1);
    }

    private void quickNor(int[] arr, int left, int right) {
        Deque<Integer> stack = new ArrayDeque<>();
        int pivot = partition1(arr, left, right);
        //分割后的子序列长度不为1，为1就没必要用partition了，因为left == right
        if(pivot - 1 > left) {
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot + 1 < right) {
            stack.push(pivot+1);
            stack.push(right);
        }
        while(!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition1(arr, left, right);
            if(pivot - 1 > left) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot + 1 < right) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

    private void quick(int[] arr, int start, int end) {
        if(start >= end) {
            return;
        }
        //  当子序列长度为7（可为其他值）时，使用插入排序对其进行排序
        if(end - start + 1 <= 7) {
            insertSortRange(arr, start, end);
            return;
        }
        int pivot = partition1(arr, start, end);
        quick(arr, start, pivot-1);
        quick(arr, pivot+1, end);
    }

    private int partition1(int[] arr, int left, int right) {
        int midIndex = getMiddleNumIndex(arr, left, right);
        swap(arr, midIndex, left);
        int tmp = arr[left];
        int tmpLeft = left;
        while(left < right) {
            while(left < right && tmp <= arr[right]) {
                right--;
            }
            while(left < right && tmp >= arr[left]) {
                left++;
            }
            swap(arr, left, right);
        }
        swap(arr, tmpLeft, left);
        return left;
    }
    private int partition2(int[] arr, int left, int right) {
        int tmp = arr[left];
        while(left < right) {
            while(left < right && arr[right] >= tmp) {
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] <= tmp) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }
    private int getMiddleNumIndex(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
        if(arr[left] < arr[right]) {
            if(arr[mid] < arr[left]) {
                return left;
            }else if(arr[right] < arr[mid]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(arr[mid] < arr[right]) {
                return right;
            }else if(arr[left] < arr[mid]) {
                return left;
            }else {
                return mid;
            }
        }
    }
    private void insertSortRange(int[] arr, int left, int right) {
        for(int i = left + 1; i <= right; i++) {
            int j = i - 1;
            int tmp = arr[i];
            while(j >= 0) {
                if(arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
                j--;
            }
            arr[j+1] = tmp;
        }
    }
    public void mergeSort(int[] arr) {
        mergeSortTmp(arr, 0, arr.length-1);
    }
    private void mergeSortTmp(int[] arr, int left, int right) {
        if(left >= right) return;
        //分解
        int mid = (left + right) / 2;
        mergeSortTmp(arr, left, mid);
        mergeSortTmp(arr, mid+1, right);

        //合并
        merge(arr, left, mid, right);
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int[] tmp = new int[right-left+1];
        int k = 0;
        int s1 = left;
        int s2 = mid+1;
        while(s1 <= mid && s2 <= right) {
            if(arr[s1] <= arr[s2]) {
                tmp[k++] = arr[s1++];
            }else {
                tmp[k++] = arr[s2++];
            }
        }
        while(s1 <= mid) {
            tmp[k++] = arr[s1++];
        }
        while(s2 <= right) {
            tmp[k++] = arr[s2++];
        }

        for(int i = 0; i < k; i++) {
            arr[i+left] = tmp[i];//注意arr和tmp的下标映射关系，arr需要加一个left
        }
    }

    public void mergeSortNor(int[] arr) {
        int gap = 1;
        while(gap <= arr.length) {
            for(int i = 0; i < arr.length; i += 2 * gap) {
                int left = i;
                int mid = left + gap - 1;
                if(mid >= arr.length) {
                    mid = arr.length - 1;
                }
                int right = mid + gap;
                if(right >= arr.length - 1) {
                    right = arr.length - 1;
                }
                merge(arr, left, mid, right);
            }
            gap *= 2;
        }
    }

}
